![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
We often see systems that use a proprietary variant of an existing cipher, altered in some hopefully security-neutral way to prevent that system from interoperating with standard implementations of the cipher. A family key is a way of designing this into the algorithm: each different family key is used to define a different variant of the cipher. In some sense, the family key is like an additional key to the cipher, but in general, it is acceptable for the family key to be very computationally expensive to change. We would expect nearly all Twofish implementations that used any family key to use only one family key.
Our goals for the family key algorithm are as follows:
A Twofish family key is simply a 256-bit random Twofish key. This key, FK, is used to derive several blocks of bits, as follows:
Note the properties of the alterations made by any family key:
Effects of Family Keys on Cryptanalysis. We are not aware of any substantial difference in the difficulty of cryptanalyzing the family key version of the cipher rather than the regular version. The ciphers operations are unchanged by the family key; only subkey and S-box generation are changed. However, they are changed in simple ways; the S-boxes are generated in exactly the same way as before, but the key material provided to them is processed in a simple way first; the round subkeys are generated in the same way as before (again, with the key material processed in a simple way first), and then have a constant 64-bit value XORed in. Related-key attacks of the kind we have been able to consider are made slightly harder, rather than easier, by this 64-bit value. The new constants XORed into the whitening subkeys simply permute the input and output space of the cipher in a very simple way.
Related Keys across Family Keys. Related-key attacks under the same family key appear, as we said above, to be at least as hard as related-key attacks in normal Twofish. There is still the question, however, of whether there are interesting related keys across different family keys. It is hard to see how such related keys would be used, but the analysis may be worth pursuing anyway.
An interesting question, from the perspective of an attacker, is whether there ar e pairs of keys that give identical subkeys except for the constant values XORed into them, and that also give identical S-boxes. By allowing an attacker to put a constant XOR into all round subkeys, such pairs of keys would provide a useful avenue of attack.
This can be done by finding a pair of related family keys, FK, FK*, that are identical in their first 128 bits, and a pair of 128-bit cipher keys, M, M*, such that M generates the same set of S-boxes with FK that M* does with FK*. For a random pair of M, M* values, this has probability 2-64 of happening, Thus, an attacker given complete control over M, M* and knowledge of FK, FK* can find such a pair of keys and family keys. However, this does not seem to translate into any kind of clean related-key attack; the attacker must actually choose the specific keys used.
We do not consider this to be a valid attack against the system. In general, related-key attacks between family keys seem unrealistic, but one which also requires the attacker to be able to choose specific key values he is trying to recover is also pointless.
A Valid Related-key Attack. An attacker can also try to find quadruples FK, FK*, M, M* such that the subkey generation and the S-box generation both get identical values. This requires that
T0 ⊕ M = T0* ⊕ M*
T1 ⊕ M = T1* ⊕ M*
If FK, FK* have the property that
T0 ⊕ T0* = T1 ⊕ T1* = δ
then related-key pairs M, M ⊕ Ϙ will put a fixed XOR difference into every round subkey, and may allow some kind of related-key attack. Again, we do not think this is an interesting attack; the attacker must force the family keys to be chosen this way, since the probability that any given pair of family keys will work this way is (for 128-bit cipher keys) 2-128. We do not expect such relationships to occur by chance until about 264 family keys are in use.
Previous | Table of Contents | Next |